package xu.dp.solution;

public class Solution1049 {
    /*
     * 最后一块石头的重量 ii
     * 很多动态规划的题目都可以转化成为动态规划的经典问题，比如这一道题目就可以转换为 01 背包问题。
     * 首先，这个问题看成将石头块分成两堆，然后求这两堆石块重量之差的最小值。那么就可以先求出石块的重量
     * 之和，然后除以 2，得到石块重量之和的一半，记为 half。这个 half 就可以当成我们背包的容量。
     * dp[i][j] 表示将前 i 个石块装入容量为 j 的背包所能获得的最大重量。那么
     * 当 stones[i] > j 时，表示第 i 个石块的重量大于背包的容量，那么 dp[i][j] = dp[i - 1][j]
     * 当 stones[i] <= j 时，有两种情况，将第 i 个石块装入背包或者不装入背包，
     * dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i])
     */
}
